/*
  中点Bresenham算法 ：
  Bresenham算法是计算机图形学典型的直线光栅化算法，由Jack E.Bresenham于1962年在IBM工作时提出。
*/
#include "OpenGLCase3.h"

void bresenhamLine(int x0, int y0, int x1, int y1, HDC hdc) {
	// 直线的斜截式表示： y = kx + b;
	// 隐式方程 F(x, y) = y - kx - b = 0; 
	// 其中 k = dy / dx = (y1 - y0) / (x1 - x0)
	// 直线上的点 F(x, y) = 0
	// 直线上方的点 F(x, y) > 0;
	// 直线下方的点 F(x, y) < 0;
	// 那么对于判断直线更偏近于那一个点，则只需要判断直线下一个穿过的2点之间的中点M，在线上方还是下方即可。
	// 那么对于点M 则可以构建判别式：d = F(xm, ym) = F(xi + 1, yi + 0.5) = yi + 0.5 - k * (xi + 1) - b
	// d < 0 时，取Pu(右上方的点) y + 1， d = 0 时， 任取一个点 Pd ， y 不变， d > 0 时，取 正右方的点 Pd ，y 不变
	// 经过递推
	// d < 0 时
	// d = F(xi + 2, yi + 1.5)
	//   = yi + 1.5 - k *（xi + 2）- b
	//   = yi + 1.5 - k *（xi + 1）- b - k
	//   = d + 1 - k
	// d >= 0 时
	// d = F(xi + 2, yi + 0.5)
	//   = yi + 0.5 - k *（xi + 2）- b
	//   = yi + 0.5 - k *（xi + 1）- b - k
	//   = d - k
	// 带入x0,y0计算得到d的初值等于 0.5 - k
	// 上述算法仍然存在浮点运算，由于对于d只需要知道符号位，则可以进行放大处理。
	// 存在 k = dy / dx, 这里需要放大 dx倍 而 0.5 需要放大2倍，所以，可以得到 放大2dx倍即可；

	int dx, dy, x, y;
	x = x0;
	y = y0;
	dx = x1 - x0;
	dy = y1 - y0;

	//float k = (dy / dx);
	//float d = 0.5 - k;
	// 放大 2dx 倍
	//int d = (0.5 - (dy / dx)) * 2 * dx;
	int k = dy;
	int d = dx - 2 * dy;

	int increUp = dx - dy; // d = d + 1 - k;
	int increDown = dy; // d = d - k;

	for (; x < x1; x++) {
		SetPixel(hdc, x, y, RGB(255, 255, 0));
		if (d < 0) {
			y += 1;
			d = d + increUp;
		}
		else {
			d = d - increDown;
		}
	}
}

// 改进的 bresenham 算法
void bresenhamLine1(int x0, int y0, int x1, int y1, HDC hdc) {
	int dx, dy, x, y;
	x = x0;
	y = y0;
	dx = x1 - x0;
	dy = y1 - y0;

	int e = -dx;

	for (; x < x1; x++) {
		SetPixel(hdc, x, y, RGB(255, 255, 0));
		e = e + 2 * dy;
		if (e > 0) {
			y++;
			e = e - 2 * dx;
		}
	}

}

void runCase3() {

	// 获取一个可供画图的DC，我这里就直接用桌面算了
	HDC hdc = GetWindowDC(GetDesktopWindow());
	//bresenhamLine(100, 100, 900, 300, hdc);
	//bresenhamLine(100, 100, 900, 700, hdc);
	bresenhamLine1(100, 100, 900, 300, hdc);
}
